00100	                          WORD BIT REVERSAL
00200	
00300	                              Baumgart

00400	
00500	
00600	ABSTRACT:	Thirty or so PDP-10 programs for reversing the  order
00700	of  the  bits  in  a  word are presented and anaylsed; although these
00800	programs were written for their peculiar  entertainment  value,  they
00900	are  subsequently discussed with respect to proving their correctness
01000	and equivalence and with respect to generating
01100	arbitrary repacking programs automatically.
01200	
01300		A series	-	Simple Serial.
01400		B series	-	Gosper Triple Tricky.
01500		C series	-	Byte Serial.
01600		D series	-	Nested Byte Swapping.
01700		E series	-	Schroeppel Bit-Rev'ing.
01800		F series	-	Combination Schee
01900	
02000	TITLE	A1
02100	INTERN	REV			; 183 memory cycles.
02200		A←←1			;   8 words long.
02300		B←←2
02400		CNT←←3
02500		P←←17
02600	REV:	MOVEI	CNT,=36		;1
02700	L:	LSHC	1		;36
02800		EXCH	A,B		;36
02900		LSHC	-1		;36
03000		EXCH	A,B		;36
03100		SOJG	CNT,L		;36
03200		MOVE	A,B		;1
03300		POPJ	P,		;1
03400	END
03500	
03600	TITLE	A2
03700	INTERN	REV				; 57 memory cycles.
03800		A←←1				;  7 words.
03900		B←←2
04000		PTR←←3
04100		P←←17
04200	REV:	MOVE	PTR,[POINT 1,B,-1]	;1
04300	L:	IDPB	A,PTR			;18 average
04400		LSH	A,-1			;18 average
04500		JUMPN	A,L			;18 average
04600		MOVE	A,B
04700		POPJ	P,
04800	END
     

00100	The Gosper triple tricky is merely the observation that
00200		TRCE	PAIR
00300		TRCE	PAIR
00400		TRCE	PAIR
00500	will swap two bits in the right half of the ac; where PAIR is a 
00600	suitable mask indicating the two bit position you wish to swap.
00700	One might hope that this code fragment could be the basis of
00800	a good REV program.
00900	
01000	TITLE	B1	TRIPLE TRICKY with COMPUTED MASK.
01100	INTERN	REV			; 156 memory cycles.
01200		A←←1			;  12 words long.
01300		P←←17
01400		LBIT←2
01500		RBIT←3
01600		MASK←4
01700	REV:	MOVEI	RBIT,1		; 1
01800		HRLZI	LBIT,400000	; 1
01900	L:	MOVE	MASK,LBIT	;18
02000		IOR	MASK,RBIT	;18
02100		TDCE	A,MASK		;18
02200		TDCE	A,MASK		;13.5
02300		TDCE	A,MASK		;13.5
02400		LSH	LBIT,-1		;18
02500		CAMN	LBIT,RBIT	;18
02600		POPJ	P,		; 1
02700		LSH	RBIT,1		;18
02800		JRST	L		;18
02900	END
03000	
03100	TITLE	B2	TRIPLE TRICKY with TABLE MASK.
03200	INTERN	REV				;101 memory cycles.
03300		A←←1				; 25 words long.
03400		CNT←←2
03500		MASK←←3
03600	REV:	MOVEI	CNT,=18			; 1
03700	L:	MOVE	MASK,TABLE(CNT)		;18
03800		TDCE	A,MASK			;18
03900		TDCE	A,MASK			;13.5
04000		TDCE	A,MASK			;13.5
04100		SOJG	CNT,L			;18
04200		POPJ	P,			; 1
04300	TABLE:	FOR I←0,=17{
04400		((1B0)⊗(-I))∨(1⊗I)}
04500	END
     

00100	BYTE SERIAL SCHEMES
00200	
00300	TITLE	C1	NAIVE STRAIGHT TABLE LOOKUP IN THREE 12-BIT BYTES.
00400	INTERN	REV
00500		A←←1
00600		B←←2
00700		X←←3
00800		P←←17
00900	REV:	LDB	X,[POINT 12,A,11]
01000		MOVE	X,TABLE(X)
01100		DPB	X,[POINT 12,A,35]
01200		LDB	X,[POINT 12,A,23]
01300		MOVE	X,TABLE(X)
01400		DPB	X,[POINT 12,B,23]
01500		LDB	X,[POINT 12,A,35]
01600		MOVE	X,TABLE(X)
01700		DPB	X,[POINT 12,B,11]
01800		MOVE	A,B
01900		POPJ	P,
02000	END
02100	
02200	
02300	TITLE C2
02400	INTERN REV				;34 memory cycles.
02500		A←←1				;72 words long.
02600		AA←←2
02700		BB←←3
02800		CNT←←4
02900		PTR←←5
03000		P←←17
03100	REV:	MOVE	PTR,[POINT 6,A,-1]	;1
03200		MOVEI	CNT,6			;1
03300	L:	ILDB	AA,PTR			;6
03400		MOVE	AA,TABLE(AA)		;6
03500		LSHC	AA,-6			;6
03600		SOJG	CNT,L			;6
03700		MOVE	A,BB			;1
03800		POPJ	P,			;1
03900	END
     

00100	TITLE	D1
00110	INTERN REV				;27 memory cycles.
00120		A←←1				;25 words long.
00130		B←←2
00140		C←←3
00200	REV:	MOVS	A
00300		ROTC	9
00400		HRL	A,
00500		MOVE	C,A
00600		AND	C,[007007007007]
00700		LSH	C,6
00800		MOVE	B,A
00900		AND	B,[070070070070]
01000		IOR	C,B
01100		LSH	A,-6
01200		AND	A,[007007007007]
01300		IORB	A,C
01400		AND	C,[111111111111]
01500		LSH	C,2
01600		MOVE	B,A
01700		AND	B,[222222222222]
01800		IOR 	C,B
01900		LSH	A,-2
02000		AND	A,[111111111111]
02100		IOR	A,C
02200		POPJ	P,
02300	END